GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Philosophenproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Philosophenproblem</h1>

</header>

</div>

Beim Philosophenproblem (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> dining philosophers problem) handelt es sich um ein Fallbeispiel aus dem Bereich der <a href="Theoretische_Informatik" title="Theoretische Informatik">theoretischen Informatik</a>. Damit soll das Problem der <a href="Nebenl%C3%A4ufigkeit" title="Nebenläufigkeit">Nebenläufigkeit</a> und die Gefahr der <a href="Verklemmung" class="mw-redirect" title="Verklemmung">Verklemmung</a> von Prozessen veranschaulicht werden. Das Problem wurde von <a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Edsger W. Dijkstra</a> formuliert.

<div class="mw-heading mw-heading2"><h2 id="Aufbau">Aufbau</h2></div>

Fünf <a href="Philosoph" title="Philosoph">Philosophen</a>, nummeriert von eins bis fünf, leben in einem Haus, in dem der Tisch für sie gedeckt ist, wobei jeder Philosoph seinen eigenen Platz am Tisch hat. Ihr einziges Problem – neben dem der <a href="Philosophie" title="Philosophie">Philosophie</a> – ist, dass es sich bei dem servierten Gericht um eine sehr schwierige Sorte Spaghetti handelt, die mit zwei Gabeln gegessen werden muss. Zwischen den Tellern befindet sich jeweils eine Gabel, sodass dies für einen einzelnen Philosophen kein Problem darstellt. Allerdings können zwei Nachbarn nicht gleichzeitig essen.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Problem">Problem</h2></div>

Die Philosophen sitzen am Tisch und denken über philosophische Probleme nach. Wenn einer hungrig wird, greift er zuerst die Gabel links von seinem Teller, dann die auf der rechten Seite und beginnt zu essen. Wenn er satt ist, legt er die Gabeln wieder zurück und beginnt wieder zu denken. Sollte eine Gabel nicht an ihrem Platz liegen, wenn der Philosoph sie aufnehmen möchte, so wartet er, bis die Gabel wieder verfügbar ist.

Solange nur einzelne Philosophen hungrig sind, funktioniert dieses Verfahren. Es kann aber passieren, dass sich alle fünf Philosophen gleichzeitig entschließen, zu essen. Sie ergreifen also alle gleichzeitig ihre linke Gabel und nehmen damit dem jeweils links von ihnen sitzenden Kollegen dessen rechte Gabel weg. Nun warten alle fünf darauf, dass die rechte Gabel wieder auftaucht. Das passiert aber nicht, da keiner der fünf seine linke Gabel zurücklegt. Die Philosophen verhungern.

<div class="mw-heading mw-heading2"><h2 id="Lösung_mittels_Ressourcenhierarchie">Lösung mittels Ressourcenhierarchie</h2></div>

Bei der Ressourcenhierarchie-Lösung werden die Gabeln von eins bis fünf durchnummeriert. Jeder Philosoph muss immer zuerst versuchen, die Gabel mit der niedrigeren Nummer aufzunehmen, und nur wenn das erfolgreich war, versucht er, die Gabel mit der höheren Nummer aufzunehmen. In diesem Fall können nicht alle fünf Philosophen gleichzeitig die Gabel mit der niedrigeren Nummer aufnehmen. Entweder nimmt der erste Philosoph die Gabel mit der Nummer eins (die zu seiner linken), oder der letzte Philosoph nimmt diese Gabel (die zu seiner rechten). Nimmt der erste Philosoph diese Gabel, so erhält der vorletzte Philosoph zwei Gabeln und der letzte keine. Nimmt der letzte Philosoph diese Gabel, so erhält der erste Philosoph keine Gabel und der letzte und vorletzte Philosoph streiten sich um die Gabel mit der Nummer fünf, wer zuerst kommt, isst mit zwei Gabeln.

Der folgende Quellcode ist eine <a href="C%2B%2B" title="C++">C++</a>11-Implementierung der Ressourcenhierarchie-Lösung für drei Philosophen. Die Funktion sleep_for() simuliert die Zeit, die normalerweise mit Geschäftslogik verbracht wird.

<div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre>#include <iostream>

#include <chrono>

#include <mutex>

#include <thread>

#include <random>

#include <ctime>

using namespace std;

int myrand(int min, int max) {

static mt19937 rnd(time(nullptr));

return uniform_int_distribution<>(min,max)(rnd);

}

void phil(int ph, mutex& ml, mutex& mh, mutex& mo) {

for (;;) { // verhindert, dass Thread beendet wird

int duration = myrand(200, 800);

{

// Block { } begrenzt Gueltigkeit von lock

lock_guard<mutex> moGuard(mo);

cout<<ph<<" denkt "<<duration<<"ms\n";

}

this_thread::sleep_for(chrono::milliseconds(duration));

{

cout<<"\t\t"<<ph<<" ist hungrig\n";

}

{

lock_guard<mutex> mlGuard(ml);

lock_guard<mutex> mhGuard(mh);

duration = myrand(200, 800);

{

cout<<"\t\t\t\t"<<ph<<" isst "<<duration<<"ms\n";

}

}

int main() {

cout<<"speisende Philosophen C++11 mit Ressourcenhierarchie\n";

mutex m1, m2, m3; // 3 Gabeln sind 3 Mutexe

mutex mo; // für ordentliche Ausgabe

// 3 Philosophen sind 3 Threads

thread t1([&] {phil(1, m1, m2, mo);});

thread t2([&] {phil(2, m2, m3, mo);});

thread t3([&] {phil(3, m1, m3, mo);}); // Ressourcenhierarchie

t1.join(); // verhindert, dass Threads beendet werden

t2.join();

t3.join();

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Alternative_Lösung">Alternative Lösung</h2></div>

Bei dieser Variante muss jeder hungrige Philosoph entweder beide Gabeln gleichzeitig, oder keine Gabeln aufnehmen. Es ist nicht gestattet, nur eine aufzunehmen, wenn die zweite nicht verfügbar ist. Allerdings ist es in diesem Fall möglich, dass zum Beispiel immer abwechselnd Philosoph eins und drei und dann Philosoph zwei und vier essen. In diesem Fall verhungert der fünfte Philosoph.

<div class="mw-heading mw-heading2"><h2 id="Zweck_des_Philosophenproblems">Zweck des Philosophenproblems</h2></div>

Das Szenario der fünf (gelegentlich auch nur drei oder vier) speisenden Philosophen wird oft gebraucht, um das Problem der <a href="Interprozesskommunikation" title="Interprozesskommunikation">Interprozesskommunikation</a> und <a href="Ressource#Informatik" title="Ressource">Ressourcenverwaltung</a> bei der Entwicklung von <a href="Betriebssystem" title="Betriebssystem">Betriebssystemen</a> zu illustrieren.

Das Beispiel soll darstellen, was passieren kann, wenn parallele <a href="Prozess_(Informatik)" title="Prozess (Informatik)">Prozesse</a> auf mehrere gemeinsame <a href="Ressource#Informatik" title="Ressource">Ressourcen</a> angewiesen sind und <a href="Nebenl%C3%A4ufigkeit" title="Nebenläufigkeit">gleichzeitig</a> darauf zugreifen. Dann kann es passieren, dass alle blockiert sind und auf ein Ereignis warten, das durch diese Blockade nie eintreffen wird. Ein solcher Zustand wird als <a href="Deadlock_(Informatik)" title="Deadlock (Informatik)">Deadlock</a> oder Verklemmung bezeichnet.

Zur Lösung des Problems werden typischerweise fortschrittliche <a href="Mutex" title="Mutex">Mutexe</a> oder <a href="Semaphor_(Informatik)" title="Semaphor (Informatik)">Semaphore</a> zur <a href="Sequentialisierung" title="Sequentialisierung">Sequentialisierung</a> verwendet, zum Beispiel scoped_lock von C++17.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Erzeuger-Verbraucher-Problem" title="Erzeuger-Verbraucher-Problem">Erzeuger-Verbraucher-Problem</a></li>

<li><a href="Raucherproblem" title="Raucherproblem">Raucherproblem</a></li>

<li><a href="Verhungern_(Informatik)" title="Verhungern (Informatik)">Verhungern (Informatik)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Abraham Silberschatz & James L. Peterson: Operating Systems Concepts. Addison-Wesley 1988, ISBN 0-201-18760-4</li>

<li>K. Mani Chandy & Jayadev Misra: The Drinking Philosophers Problem. In: ACM Transactions on Programming Languages and Systems. Vol. 6, No. 4, Oktober 1984, S. 632–646 (<a rel="nofollow" class="external text" href="https://www.cs.utexas.edu/users/misra/scannedPdf.dir/DrinkingPhil.pdf">PDF; 960 kB</a>)</li>

<li><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Edsger W. Dijkstra</a>: Hierarchical ordering of sequential processes. In: Acta Informatica. 1(2), 1971, S. 115–138 (<a rel="nofollow" class="external text" href="https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF">PDF; 1,0 MB</a>)</li>

<li>Daniel J. Lehmann & <a href="Michael_O._Rabin" title="Michael O. Rabin">Michael O. Rabin</a>: On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. In: Principles Of Programming Languages 1981 (POPL ’81). 1981, S. 133–138</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.heise.de/developer/artikel/Dining-Philiosophers-Problem-I-6320973.html">Dining Philiosophers Problem I</a> (deutsch)</li>

<li><a rel="nofollow" class="external text" href="https://www.heise.de/developer/artikel/Dining-Philosopher-Problem-II-6327946.html">Dining Philosopher Problem II</a> (deutsch)</li>

<li><a rel="nofollow" class="external text" href="https://www.heise.de/developer/artikel/Dining-Philosophers-Problem-III-6335228.html">Dining Philosophers Problem III</a> (deutsch)</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20190103144139/http://laser.cs.umass.edu/verification-examples/dp_standard/dp.html">Discussion of the problem with solution code for 2 or 4 philosophers</a> (englisch)</li>

<li><a rel="nofollow" class="external text" href="http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?Dining+Philosophers+Problem">Discussion of various solutions 1</a> (englisch)</li>

<li><a rel="nofollow" class="external text" href="https://www.cs.utk.edu/~plank/plank/classes/cs560/560/notes/Dphil/lecture.html">Discussion of various solutions 2</a> (englisch)</li>

<li><a rel="nofollow" class="external text" href="https://www.doc.ic.ac.uk/~jnm/concurrency/classes/Diners/Diners.html">Interactive example</a> of the Philosophers problem (englisch) [als <a href="Java-Applet" title="Java-Applet">Java-Applet</a>, gelten inzwischen als veraltet]</li>

<li><a rel="nofollow" class="external text" href="https://www.crockford.com/ec/dining.html">Satan Comes to Dinner</a> (englisch)</li>

<li><a rel="nofollow" class="external text" href="https://www.cs.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html">ThreadMentor</a> (englisch)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Dijkstra, E. W. (1971, June). <a rel="nofollow" class="external text" href="https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF">EWD310 Hierarchical ordering of sequential processes</a>. Acta Informatica 1(2): 115–138

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> <a rel="nofollow" class="external text" href="https://en.cppreference.com/w/cpp/thread/scoped_lock">std::scoped_lock - cppreference.com.</a> Abgerufen am 15. Januar 2022.<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3APhilosophenproblem&rft.title=std%3A%3Ascoped_lock+-+cppreference.com&rft.description=std%3A%3Ascoped_lock+-+cppreference.com&rft.identifier=https%3A%2F%2Fen.cppreference.com%2Fw%2Fcpp%2Fthread%2Fscoped_lock">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-12-04" href="https://de.wikipedia.org/wiki/?title=Philosophenproblem&oldid=262133310">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>